package algorithms.question.class08;

import common.util.MyUtil;

/**
 * 给定一个char[][] matrix，也就是char类型的二维数组，再给定一个字符串word，
 * 可以从任何一个某个位置出发，可以走上下左右，能不能找到word？
 * char[][] m =  {
 * { 'a', 'b', 'z' },
 * { 'c', 'd', 'o' },
 * { 'f', 'e', 'o' }
 * }
 * 设定1：可以走重复路的情况下，返回能不能找到
 * 比如，word = "zoooz"，是可以找到的，z -> o -> o -> o -> z，因为允许走一条路径中已经走过的字符
 * 设定2：不可以走重复路的情况下，返回能不能找到
 * 比如，word = "zoooz"，是不可以找到的，因为允许走一条路径中已经走过的字符不能重复走
 *
 * @author guichang
 * @date 2021/8/5
 */

@SuppressWarnings("all")
public class Code3_二位数组能否找到字符串 {

    public static void main(String[] args) {
        char[][] matrix = {
                {'a', 'b', 'z'},
                {'c', 'd', 'o'},
                {'f', 'e', 'o'}
        };
        String str = "zoo";
        MyUtil.printf("可以走重复路找到{}，结果：{}", str, canBeRepeated(matrix, str));
        MyUtil.printf("不可以走重复路找到{}，结果：{}", str, canNotBeRepeated(matrix, str));
    }

    /**
     * 可以改动态规划
     * 可以走重复路
     */
    public static boolean canBeRepeated(char[][] matrix, String str) {
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0 || str == null || str == "") {
            return false;
        }
        char[] strs = str.toCharArray();
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[0].length; j++) {
                if (processRepeated(matrix, strs, i, j, 0)) {
                    return true;
                }
            }
        }
        return false;
    }

    /**
     * 可以走重复路的情况下，从(i,j)开始能否走出从k开始的路
     */
    private static boolean processRepeated(char[][] matrix, char[] strs, int i, int j, int k) {
        if (i < 0 || j < 0 || i == matrix.length || j == matrix[0].length) {
            return false;
        }
        // 能走到头表示可以走出str
        if (k == strs.length) {
            return true;
        }
        // 首字母对不上直接false
        if (matrix[i][j] != strs[k]) {
            return false;
        }
        // 开始走路
        // 上下左右
        boolean p1 = processRepeated(matrix, strs, i - 1, j, k + 1);
        boolean p2 = processRepeated(matrix, strs, i + 1, j, k + 1);
        boolean p3 = processRepeated(matrix, strs, i, j - 1, k + 1);
        boolean p4 = processRepeated(matrix, strs, i, j + 1, k + 1);
        // 有一次能成功就算成功
        return p1 || p2 || p3 || p4;
    }

    /**
     * 不可以走重复路
     * 不能改动态规划，可变参数较多
     */
    public static boolean canNotBeRepeated(char[][] matrix, String str) {
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0 || str == null || str == "") {
            return false;
        }
        char[] strs = str.toCharArray();
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[0].length; j++) {
                if (processNotRepeated(matrix, strs, i, j, 0)) {
                    return true;
                }
            }
        }
        return false;
    }

    /**
     * 不可以走重复路的情况下，从(i,j)开始能否走出从k开始的路
     */
    private static boolean processNotRepeated(char[][] matrix, char[] strs, int i, int j, int k) {
        if (i < 0 || j < 0 || i == matrix.length || j == matrix[0].length) {
            return false;
        }
        // 能走到头表示可以走出str
        if (k == strs.length) {
            return true;
        }
        // 首字母对不上直接false
        if (matrix[i][j] != strs[k]) {
            return false;
        }
        // 到这里matrix[i][j]==strs[k]，所以不用记录
        // 防止重复
        matrix[i][j] = 0;
        // 开始走路
        // 上下左右
        boolean p1 = processNotRepeated(matrix, strs, i - 1, j, k + 1);
        boolean p2 = processNotRepeated(matrix, strs, i + 1, j, k + 1);
        boolean p3 = processNotRepeated(matrix, strs, i, j - 1, k + 1);
        boolean p4 = processNotRepeated(matrix, strs, i, j + 1, k + 1);
        // 有一次能成功就算成功
        boolean res = p1 || p2 || p3 || p4;
        // 需要恢复，很重要！！！
        matrix[i][j] = strs[k];
        return res;
    }
}